#pragma once
#include<iostream>
#include<utility>
using namespace std;

enum col
{
	RED,
	BLACK
};

template<class T>
class TreeNode
{
public:

	TreeNode(T& val = T())
		:_val(val)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}

	TreeNode(const T& val = T())
		:_val(val)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}

	T _val;
	TreeNode<T>* _left;
	TreeNode<T>* _right;
	TreeNode<T>* _parent;
	col _col;
};

template<class T>
class __iterator
{
public:
	typedef TreeNode<T> Node;
	typedef __iterator<T> self;

	__iterator(Node* node)
		:_node(node)
	{}

	T& operator*()
	{
		return _node->_val;
	}

	T* operator->()
	{
		return &(_node->_val);
	}

	self& operator++()
	{
		if (_node->_right)
		{
			Node* subright = _node->_right;

			while (subright->_left)
			{
				subright = subright->_left;
			}

			_node = subright;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;

			while (parent)
			{
				if (parent->_left == cur)
				{
					break;
				}
				else
				{
					cur = cur->_parent;
					parent = parent->_parent;
				}
			}

			_node = parent;
		}

		return *this;
	}

	self operator++(int)
	{
		Node* prev = _node;
		++this;
		return *prev;
	}

	self& operator--()
	{
		if (_node->_left)
		{
			Node* subleft = _node->_left;

			while (subleft->_right)
			{
				subleft = subleft->_right;
			}

			_node = subleft;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;

			while (parent)
			{
				if (cur == parent->_right)
				{
					break;
				}
				else
				{
					cur = parent;
					parent = parent->_parent;
				}
			}

			_node = parent;
		}

		return *this;
	}

	self operator--(int)
	{
		Node* prev = _node;
		--this;
		return *prev;
	}

	bool operator==(const self& other) const
	{
		if (this->_node == other._node)
		{
			return true;
		}

		return false;
	}

	bool operator!=(const self& other) const
	{
		return !(*this == other);
	}

private:
	Node* _node;
};

template<class k,class T,class KeyOfT>
class RedBlackTree
{
public:
	typedef TreeNode<T> Node;
	typedef __iterator<T> iterator;
	KeyOfT OfT;

	RedBlackTree()
		:_root(nullptr)
	{}

	iterator begin()
	{
		Node* cur = _root;

		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return iterator(cur);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	iterator find(const k& key)
	{
		Node* cur = _root;
		KeyOfT OfT;

		while (cur)
		{
			if (key < OfT(cur->_val))
			{
				cur = cur->_left;
			}
			else if (key > OfT(cur->_val))
			{
				cur = cur->_right;
			}
			else
			{
				return iterator(cur);
			}
		}

		return iterator(nullptr);
	}

	bool insert(const T& t) 
	{
		if (_root == nullptr)
		{
			_root = new Node(t);
		}
		else
		{
			Node* cur = _root;
			Node* parent = nullptr;
			k key = OfT(t);

			while (cur)
			{
				if (key > OfT(cur->_val))
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key == OfT(cur->_val))
				{
					return false;
				}
				else if (key < OfT(cur->_val))
				{
					parent = cur;
					cur = cur->_left;
				}
			}

			cur = new Node(t);
			if (OfT(parent->_val) < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			cur->_parent = parent;

			while (parent && parent->_col == RED)
			{
				Node* Grandfather = parent->_parent;

				if (Grandfather->_left == parent)
				{
					Node* Uncle = Grandfather->_right;

					if (Uncle && Uncle->_col == RED)
					{
						Uncle->_col = parent->_col = BLACK;
						Grandfather->_col = RED;

						cur = Grandfather;
						parent = cur->_parent;
					}
					else if (!Uncle || Uncle->_col == BLACK)
					{
						if (parent->_left == cur)
						{
							Rotater(Grandfather);

							parent->_col = BLACK;
							Grandfather->_col = RED;
							break;
						}
						else
						{
							Lotater(parent);
							Rotater(Grandfather);

							cur->_col = BLACK;
							Grandfather->_col = RED;
							break;
						}
					}
				}
				else
				{
					Node* Uncle = Grandfather->_left;

					if (Uncle && Uncle->_col == RED)
					{
						Uncle->_col = parent->_col = BLACK;
						Grandfather->_col = RED;

						cur = Grandfather;
						parent = cur->_parent;
					}
					else if (!Uncle || Uncle->_col == BLACK)
					{
						if (parent->_right == cur)
						{
							Lotater(Grandfather);

							parent->_col = BLACK;
							Grandfather->_col = RED;
							break;
						}
						else
						{
							Rotater(parent);
							Lotater(Grandfather);

							cur->_col = BLACK;
							Grandfather->_col = RED;
							break;
						}
					}
				}
			}
		}
		_root->_col = BLACK;

		return true;
	}

	~RedBlackTree()
	{
		del(_root);
	}

private:

	void Lotater(Node* parent)
	{
		Node* parentright = parent->_right;
		Node* rightleft = parentright->_left;
		Node* pparent = parent->_parent;

		if (pparent)
		{
			if (pparent->_left == parent)
			{
				pparent->_left = parentright;
			}
			else
			{
				pparent->_right = parentright;
			}
		}
		else
		{
			_root = parentright;
		}
		parentright->_parent = pparent;
		parentright->_left = parent;
		parent->_right = rightleft;
		parent->_parent = parentright;
		if (rightleft)
		{
			rightleft->_parent = parent;
		}
	}

	void Rotater(Node* parent)
	{
		Node* cur = parent->_left;
		Node* pparent = parent->_parent;
		Node* curright = cur->_right;

		parent->_parent = cur;
		parent->_left = curright;
		if (curright)
		{
			curright->_parent = parent;
		}
		cur->_parent = pparent;
		if (pparent != nullptr)
		{
			if (pparent->_left == parent)
			{
				pparent->_left = cur;
			}
			else
			{
				pparent->_right = cur;
			}
		}
		else
		{
			_root = cur;
		}
		cur->_right = parent;
	}

	void del(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		Node* rootleft = root->_left;
		Node* rootright = root->_right;
		delete root;

		del(rootleft);
		del(rootright);
	}

	Node *_root;
};

